//class Solution {
//public:
//    ListNode* rotateRight(ListNode* head, int k) {
//        if (k == 0) return head;
//        if (head == nullptr) return head;
//        vector<int> v;
//        ListNode* cur = head;
//        while (cur)
//        {
//            v.push_back(cur->val);
//            cur = cur->next;
//        }
//        k %= v.size();
//        reverse(v.begin(), v.end() - k);
//        reverse(v.end() - k, v.end());
//        reverse(v.begin(), v.end());
//        int i = 0;
//        ListNode* newhead = nullptr;
//        ListNode* tail = newhead;
//        while (i < v.size())
//        {
//            ListNode* node = new ListNode(v[i++]);
//            if (tail == nullptr)
//            {
//                tail = newhead = node;
//            }
//            else
//            {
//                tail->next = node;
//                tail = tail->next;
//            }
//        }
//        return newhead;
//    }
//};
//


//class Solution {
//public:
//    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
//        dfs(A, B, C, A.size());
//    }
//    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
//    {
//        if (n == 1)
//        {
//            C.push_back(A.back());
//            A.pop_back();
//            return;
//        }
//        dfs(A, C, B, n - 1);
//        C.push_back(A.back());
//        A.pop_back();
//        dfs(B, A, C, n - 1);
//    }
//};


//class Solution {
//public:
//    TreeNode* sortedArrayToBST(vector<int>& nums) {
//        return dfs(nums, 0, nums.size() - 1);
//    }
//    TreeNode* dfs(vector<int>& nums, int left, int right)
//    {
//        if (left > right) return nullptr;
//        int mid = left + (right - left) / 2;
//        TreeNode* root = new TreeNode(nums[mid]);
//        root->left = dfs(nums, left, mid - 1);
//        root->right = dfs(nums, mid + 1, right);
//        return root;
//    }
//};

